package com.company.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class LowestCommonAncestor {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //1: 获取 两个节点的 触达路径链表
        Stack<TreeNode> pNodePath = new Stack<>();
        Stack<TreeNode> qNodePath = new Stack<>();
        getAccessPath(root, p, pNodePath);
        getAccessPath(root, q, qNodePath);
        //2: 求两个链表的 最后一个公共节点

        TreeNode parentNode =null;
        TreeNode pNode=null;
        TreeNode qNode=null;
        while (!pNodePath.isEmpty()&& !qNodePath.isEmpty()){
            pNode = pNodePath.pop();
            qNode = qNodePath.pop();

            if (pNode == qNode) {
                parentNode = pNode;
                continue;
            }
            break;
        }

        return parentNode;
    }


    private boolean getAccessPath(TreeNode node, TreeNode target, Stack<TreeNode> path) {
        if (node == null) {
            return false;
        }
        if (node == target) {
            //找到目标
            path.add(node);
            return true;
        }
        if (getAccessPath(node.left, target, path)
                || getAccessPath(node.right, target, path)) {
            path.add(node);
            return true;
        }
        return false;
    }
}
